The design of very large scale integrated circuits, particularly application specific integrated circuits, is almost invariably performed with the aid of a computerized design tool, namely a data processor which is programmed with an operating program normally called a compiler. The data processor accepts user-selected inputs, which may be a high level schematic comprising icons and their interconnections. The high level specification is independent of architecture, defining the desired application specific circuit in terms of generalized functional schematic blocks. The data processor computes, employing sub-programs or macros appropriate to each signal processing function, a netlist. This is a structural level definition which includes a list of the integrated circuit hardware cells needed to achieve the functional specification. The cells are selected from a cell library, i.e. a data store of previously designed hardware cells of various functions and technical specification. The netlist also specifies wiring interconnecting the selected hardware cells. From the netlist it is readily feasible using existing computer aided design layout systems to generate the detailed mask data required to produce the particular application specific integrated circuit in chip form. Reference may be made to U.S. Pat. No. 4,922,432 issued May 1, 1990 to Kobayashi et al. for a description of the nature and use of cell libraries.
Other references which illustrate the state of the art are U.S. Pat. Nos. 4,703,435, issued Oct. 27, 1987 to Darringer et al., 4,967,367 issued Oct. 30, 1990 to Piednoir and 5,005,136 issued Apr. 2, 1991 to Van Berkel et al.
An important stage in the automated design process is called optimization of the netlist. The cell library defines various circuits such as gates, OR gates, exclusive-OR gates, flip-flops, latches, multiplexed flip-flops full adders and suchlike. The cell library also contains, in respect of each circuit, timing information by means of which the propagation time of a signal between the pins, i.e. terminals of a cell under specified conditions can be computed. Various optimization routines exist in known practice. Broadly speaking, they comprise spatial optimization routines and temporal optimization routines. In the former, a provisional netlist is analysed by the computer and, in accordance with appropriate algorithms, the provisional netlist is modified in order, for example, to utilize the area more efficiently or to reorganise the layout of the cells so as to eliminate features which are awkward or inconvenient for fabrication. As far as temporal optimization routines are concerned, the propagation time of various signals may be computed according to the information in the cell library and the provisional netlist is reorganised to improve the performance of the circuit in this respect. Generally speaking, there may be a conflict between optimization for area and an optimization for speed of performance and sophisticated optimization routines need to include algorithms which will achieve an appropriate compromise between the optimal requirements of area and timing.
One example of a netlist optimization procedure is given by copending application Ser. No. 07/356023 filed May 23rd, 1989, assigned to the same assignee as the present application.
Known optimization procedures presume that the netlist is not hierarchical, that is to say the structural specification of each cell in the netlist is self-sufficient, as exemplified by Kobayashi et al., previously cited.
However, for a variety of purposes it is useful to employ a hierarchical netlist, wherein a high-level cell in the cell library is not necessarily employed directly for the computation of the masks because it comprises a multiplicity of cells which are likewise obtained from the cell library but are more primitive than the high level cell and which themselves are employed for the conversion of the structural specification into the semiconductor mask data. More than two levels of the hierarchy are possible. For example, a high level cell could be a multiplier which contains multiple instances of a lower level cell such as an adder, which contains instances of lowest level cells such as AND and OR gates.
The main object of the present invention is to facilitate the automated optimization of a hierarchical netlist, particularly within a mechanised or computer aided process for the design, layout and fabrication of a large scale integrated circuit. A principal difficulty in the way of achieving this object is that known logic optimizers, such as the commercially available Compass v8r3.1 Logic Optimizer, are capable of optimizing only a flat (that is, non-hierarchical) netlist. Using such an optimizer, a designer who wishes to optimize a hierarchical design must choose between two methods, viz (i) flattening the netlist and then optimizing it; or (ii) optimizing each subcell individually. The first method has the disadvantage that the flattened netlist can be considerably larger than the hierarchical netlist, placing great demands on the memory and the central processing unit of the optimizer. For example, if the top-level cell contains eight instances of cell A and cell A contains thirty-two instances of cell B, the flattened netlist contains two hundred and fifty-six instances of cell B. Thus, the `flat` optimizer will spend an inordinate processing time optimizing two hundred and fifty-six essentially identical copies of the same logic. The flattened netlist could easily become so large that the `flat` optimizer cannot accommodate it.
Another disadvantage is that the resulting optimized netlist lacks hierarchy, making it difficult for the user to make further checks or alterations to the optimized netlist. It would be more convenient for the user if the optimized netlist preserved the hierarchy
The second approach would normally place a huge burden on the user, as to how to provide meaningful timing constraints for each subcell being optimized. The user would rather just specify timing constraints for the top-level cell, so that the optimizer would automatically compute appropriate constraints for each subcell.
The present invention is based on the automation of the second approach mentioned above. In broad terms, an optimizer system according to the invention receives as inputs a netlist and user-specified timing constraints. The timing constraints preferably comprise predetermined times of arrival of signals at each of a set of source nodes and required times of appearance of signals at a set of destination or output nodes. The system is arranged to compute, for each type of subcell, an abstract timing model. In essence this is a pin-to-pin timing model of the subcell. Using the specified timing constraints and the abstract timing models, the constraints are propagated, starting with the top-most cell, down through the cell hierarchy, at least as far as a target subcell. Then a flat optimizer can be employed to optimize the target subcell, or the specific instance of it, subject to the timing constraints propagated to it. Where there are multiple instances of a particular subcell, the timing constraints can be merged, so as to avoid the need for separately optimizing each instance of the subcell.
An entire hierarchical netlist may therefore be automatically optimized according to the invention by (i) selecting, using an appropriate algorithmic procedure, a subcell to be optimized; (ii) optimizing that subcell; (iii) substituting the optimized subcell for the original subcell throughout the hierarchical netlist; and (iv) repeating the procedure until all subcells have been optimized. Other features and advantages of the invention will become apparent from the description which follows.